EM 基本思想
已知观察数据,未知隐含数据和模型参数。在E步,我们所做的事情是固定模型参数的值,优化隐含数据的分布(猜想隐变量的数据),而在M步,我们所做的事情是固定隐含数据分布,优化模型参数的值(基于观测数据和猜测的隐变量数据最大化对数似然函数)
这个算法与 MLE(maximum likelihood estimation)的差别是:MLE 针对无隐变量的模型,先收集所有变量的观测数据,然后根据完整的观测数据去估计参数;EM 针对含隐变量的模型,先根据可观测变量的数据猜测隐变量的数据,然后根据隐变量数据和观测数据来估计参数
EM 推导
Jensen’s inequality
如果函数 \(g(x)\) 是凸函数,那么有 \(g(E(x))\geq E(g(x))\)
证明如下,过点 \((x, g(E(x)))\) 所一条切线,假设切线公式为 \(L(x)=a+bx\)
EM 算法
整体思想
假设有 \(n\) 个独立同分布的数据 \({x^{1}, x^{(2)},...,x^{(n)}}\),我们要估计一个包含隐变量 \(z\) 和变量 \(x\) 的模型的参数,改模型表示为 \(p(x,z;\theta)\),
那么,关于变量 \(x\) 的概率密度为 \(p(x;\theta)=\sum_{z} p(x,z;\theta)\)
模型的训练目标为极大对数似然函数 \(l(\theta)=log(\sum_{i=1}^{n}p(x^{(i)};\theta))=\sum_{i=1}^{n}\sum_{z^{(i)}}p(x^{(i)}, z^{(i)};\theta)\)。由于 \(z\) 是隐变量,数据无法观测,优化这个目标是困难的
EM 算法,通过构造 \(l(\theta)\) 的下界函数,通过在 E 步根据参数和部分观测数据计算下界函数,在 M 步最大化下界函数来实现对参数 \(\theta\) 的逐步优化
下界函数 ELBO 推导
先考虑对一个数据样例 \(x\) 的优化过程,即针对目标 \(log(p(x;\theta))=log(\sum_{z} p(x,z;\theta))\),令分布 \(Q(z)\) 为隐变量 \(z\) 的一个分布,\(\sum_{z}Q(z)=1, Q(z)\geq 0\),此时重写目标
\(log(p(x;\theta))=log(\sum_{z} p(x,z;\theta))=log\sum_{z}Q(z)\frac{p(x,z;\theta)}{Q(z)} \geq \sum_{z}Q(z)log\frac{p(x,z;\theta)}{Q(z)}\)
上面不等式根据 Jensen 不等式可推导,因为 \(log(\frac{p(x,z;\theta)}{Q(z)})\) 是一个关于 \(z\) 的凸函数
Q 函数的确定
对于任意一个 \(Q(z)\) 上面的不等式都成立,但是我们希望找到的下界函数跟目标函数足够接近(也就是令不等式的等式成立),此时必须满足条件 \(\frac{p(x,z;\theta)}{Q(z)}=c\),这意味着 \(Q(z)\sim p(x,z;\theta)\),而 \(\sum_z Q(z)=1\)(归一化概率分布),因此我们可以计算出 \(Q(z)\) 为
\(Q(z)=\frac{p(x,z;\theta)}{\sum_{z} p(x,z;\theta)}=\frac{p(x,z;\theta)}{p(x;\theta)}=p(z|x;\theta)\)
这样我们就唯一确定了 \(Q(z)\) 函数为 \(z\) 的给定观测数据 \(x\) 和参数 \(\theta\) 的后验概率,即给定了观测数据和参数,就可以猜测出 \(z\) 的概率分布(隐数据),基于此就计算出了一个新的 ELBO
EM 算法
在此重写我们的目标函数和下界函数的关系
\(l(\theta)=\sum_{i}log(p(x_i;\theta))\geq \sum_{i}ELBO(x^{(i)};Q_i(z^{(i)}),\theta)=\sum_{i}\sum_{z^{(i)}} Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\),对于任意 \(Q_i,i=1,2,...,n\) 必须满足 \(Q_i(z^{(i)})=p(z^{(i)}|x^{(i)};\theta)\)
Initialization
随机初始化 \(\theta\)
E-step
对于每一个 \(i\),令
\(Q_i(z^{(i)}):=p(z^{(i)}|x^{(i)};\theta)\)
M-step
\(\theta:=\underset{\theta}{argmax}\sum_{i}^{n} ELBO(x^{(i)};Q_i,\theta) =\underset{\theta}{argmax}\sum_{i}^{n}\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\)
收敛性证明
\(l(\theta^{(t+1)})\geq \sum_{i=1}^{n} ELBO(x^{(i)},Q_i^{(t)},\theta^{(t+1)}) \geq \sum_{i=1}^{n} ELBO(x^{(i)},Q_i^{(t)},\theta^{(t)}) =l(\theta^{(t)})\)
其中 \(\theta^{(t+1)}\) 是通过 \(\underset{\theta}{argmax} \sum_{i=1}^n ELBO(x^{(i)};Q_i^{(t)},\theta)\) 求出来的最优参数
应用
K-means 算法
K-means 算法开始给定随机的聚类簇的中心(簇的中心就是隐变量),根据聚类簇的中心划分数据。在 E 步中估计 K 个簇的中心位置。然后计算得到每个样本最近的质心,并把样本聚类到最近的这个质心,这个就是 M 步